package com.liang.leetcode.dp;

/**
 * 完全背包：在同一行找，表示当前物品是可以重复放入的
 */
public class Dp09_CompleteBagProblem {
    public static void main(String[] args) {
        // 物品的数量
        int n = 3;
        // 物品重量与价值数组
        int[] weight = {1, 3, 4};
        int[] value = {15, 20, 30};
        // 背包的容量
        int bagWeight = 4;
        System.out.println(bagComplete(n, weight, value, bagWeight));
    }

    /**
     * 解法1：动态规划
     * 返回背包能容纳的最大价值
     */
    private static int bagComplete(int n, int[] weight, int[] value, int bagWeight) {
        // dp[i][j] 表示从前 i 个物品里任意取，放进容量为 j 的背包，价值总和最大是多少
        int[][] dp = new int[n][bagWeight + 1];
        // 初始化第一行数据
        for (int j = weight[0]; j <= bagWeight; j++) {
            dp[0][j] = dp[0][j - weight[0]] + value[0];
        }
        // 先遍历物品 i，从第2个物品开始
        for (int i = 1; i < n; i++) {
            // 再遍历背包容量 j
            for (int j = 0; j <= bagWeight; j++) {
                // 背包容量 j 装不下物品 i
                if (j < weight[i]) {
                    dp[i][j] = dp[i - 1][j];
                } else {
                    // dp[i][j - weight[i]] + value[i] 表示剩余空间能装的最大价值 + 当前物品价值
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - weight[i]] + value[i]);
                }
            }
        }
        return dp[n - 1][bagWeight];
    }

    /**
     * 优化：二维数组降维
     */
    private static int bagComplete2(int n, int[] weight, int[] value, int bagWeight) {
        // dp[j] 表示背包容量为 j 时的最大价值
        int[] dp = new int[bagWeight + 1];
        // 先遍历物品 i
        for (int i = 0; i < n; i++) {
            for (int j = 0; j <= bagWeight; j++) {
                // 背包容量 j 装得下物品 i
                if (j >= weight[i]) {
                    dp[j] = Math.max(dp[j], dp[j - weight[i]] + value[i]);
                }
            }
        }
        return dp[bagWeight];
    }

}
